P ir NP lygumas
P ir NP lygumas – matematikos uždavinys, kuriame prašoma nustatyti, ar kiekviena formali kalba, priimama nedeterministinės Tiuringo mašinos per polinominį laiką taip pat gali būti per polinominį laiką priimta ir deterministinės Tiuringo mašinos.[1] Kitaip tariant, jis klausia, ar klasė P yra lygi klasei NP.[1]
Neformaliai klasei P priskiriami uždaviniai, kuriuose reikia priimti sprendimą, kurie yra išsprendžiami per skaičių žingsnių, kuris ribojamas kokio nors daugianario, priklausančio nuo įėjimo duomenų ilgio.[1]
Klasė NP iš pradžių buvo apibrėžiama remiantis nedeterministinėmis Tiuringo mašinomis, nuo to ir pavadinimas gautas sutrumpinus „nedeterministinis polinominis laikas“ (angl. nondeterministic polynomial time).[1] Vėliau ją pradėta apibrėžti remiantis patikrinimo santykiu.[1]
P ir NP lygumas buvo vienas iš septynių uždavinių, kurie 2000 m. buvo įtraukti į Tūkstantmečio premijos uždavinių sąrašą.[2]
Išnašos
[redaguoti | redaguoti vikitekstą]- ↑ 1,0 1,1 1,2 1,3 1,4 Stephen Cook „The P versus NP Problem“ // James Carlson, Arthur Jaffe, Andrew Wiles (red.) „The Millennium Prize Problems“, „American Mathematical Society“, 2006, 87-104 psl.
- ↑ Arthur M. Jaffe „The Millennium Grand Challenge in Mathematics“, „Notices of the AMS“, June/July 2000, Vol. 53, Nr. 6, p. 652-660 [1]
|
Šis su matematika susijęs straipsnis yra nebaigtas. Jūs galite prisidėti prie Vikipedijos papildydami šį straipsnį. |